package linear_list.leetcode.medium;

/**
 * @author Stark
 * @description 分割链表
 * 题目链接：https://leetcode-cn.com/problems/partition-list-lcci/
 * @date 2022/4/11 21:11
 **/
public class Num02_04_Partition {
    int choice = 1;
    public ListNode partition(ListNode head, int x) {
        if(choice == 1) {
            //方法1
            //定义一个虚拟结点,将小于x的结点都拼接到该结点的左边
            //将大于x的结点都拼接到该虚拟结点的后面
            if (head == null || head.next == null) {
                return head;
            }
            ListNode dummyNode = new ListNode(x);
            ListNode newHead = dummyNode;
            //拼接结点
            while (head != null) {
                ListNode tmp = head.next;
                if (head.val < x) {
                    head.next = newHead;
                    newHead = head;
                } else {
                    head.next = dummyNode.next;
                    dummyNode.next = head;
                }
                head = tmp;
            }
            //到这里拼接完毕
            //需要再遍历一遍找到虚拟结点的前驱,将虚拟结点删除
            //注意：需要判断是否左边或者只有右边的特殊情况
            if (newHead == dummyNode) {
                //所有结点都在虚拟结点的右面
                newHead = newHead.next;
            } else {
                ListNode cur = newHead, next = newHead.next;
                while (next != dummyNode) {
                    cur = next;
                    next = next.next;
                }
                cur.next = dummyNode.next;
            }
            return newHead;
        }else if(choice == 2){
            //方法2
            //使用两个索引,一个索引(minHead)保存小于x的结点,一个索引(maxHead)保存大于x的结点
            //遍历原链表,将小于x的结点拼接到minHead,将大于x的结点拼接到maxHead后
            //最后将两个链表拼接到一起返回minHead
            if(head == null || head.next == null)
                return head;
            ListNode minHead = new ListNode(0),curMin = minHead;
            ListNode maxHead = new ListNode(0),curMax = maxHead;
            //将对应的结点拼接到对应链表上
            while(head != null){
                if(head.val < x){
                    curMin = curMin.next = head;
                }else{
                    curMax = curMax.next = head;
                }
                head = head.next;
            }
            //将两个链表拼接起来
            curMin.next = maxHead.next;
            curMax.next = null;
            return minHead.next;
        }else if(choice == 3){
            //同样是方法二
            //这里没有使用虚拟头结点
            //明显会复杂很多!!!
            if(head == null || head.next == null)
                return head;
            ListNode minHead = null,curMin = null;
            ListNode maxHead = null,curMax = null;
            while(head != null){
                if(head.val < x){
                    if(minHead == null)
                        curMin = minHead = head;
                    else{
                        curMin = curMin.next = head;
                    }
                }else{
                    if(maxHead == null){
                        curMax = maxHead = head;
                    }else{
                        curMax = curMax.next = head;
                    }
                }
                head = head.next;
            }
            if(curMax !=null){
                curMax.next = null;
                if(curMin == null){
                    return maxHead;
                }else {
                    curMin.next = maxHead;
                    return minHead;
                }
            }else{
                curMin.next = null;
                return minHead;
            }
        }
        return null;
    }
}
